D - AtCoder Janken 3题解

题意：

高桥和青 木要玩石头剪刀布，给你一个长度为 $n$ 的字符串 $s$ ，$s$ 表示青木在第 $i$ 局游戏中的动作（R表示石头，P表示布，S表示剪刀。）。

高桥不可以在任何一局中输给青木（即：高桥和青木只可以平局或高桥赢青木），且高桥第 $i$ 局出的和第 $i-1$ 局出的不能一样，现在，问你高桥可以胜几局？

解题思路

很明显是一道 $\textrm{DP}$ 题：

定义状态:

$f_{i,j}$ 表示第 $i$ 局出 $j$ 时最多可以获胜的局数（$j = 1$时表示出石头，$j = 2$时表示出布，$j = 3$时表示出剪刀）。

初始化：

if (s[0] == 'R') {
        f[0][1] = 0;//两人一起出石头，不计分
        f[0][2] = 1;//高桥出布，高桥加一分
        //注意：高桥不可以输给青木，所以f[0][3]不可以初始化为-1
    }
    if (s[0] == 'P') {
        f[0][2] = 0;//同理
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
}

转移方程：

当$s_i =$ R 时：

$$f_{i,1} = \max(f_{i-1,2}, f_{i-1,3})\\ f_{i,2} = \max(f_{i-1,1}, f_{i-1,3}) + 1$$

（注意：$f_{i,1}$ 是被 $f_{i-1,2}$ 和 $f_{i-1,3}$转移过来的，因为高桥第 $i$ 局出的和第 $i-1$ 局出的不能一样，
高桥不可以中输给青木，所以 $j$ 不可以取 $3$ ，即：不可以出剪刀）。
当$s_i =$ P 时：

$$f_{i,2} = \max(f_{i-1,1}, f_{i-1,3})\\ f_{i,3} = \max(f_{i-1,2}, f_{i-1,3}) + 1$$

当$s_i =$ S 时：

$$f_{i,1} = \max(f_{i-1,2}, f_{i-1,3}) + 1\\ f_{i,3} = \max(f_{i-1,1}, f_{i-1,2})$$

答案就取 $\max(f_{n - 1,1},f_{n - 1,2},f_{n - 1,3})$，（我的字符串 $s$ 下标从 $0$ 开始存）。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, ans, f[N][10];
string s;
main() {
    cin >> n >> s;
    if (s[0] == 'R') {
        f[0][1] = 0;
        f[0][2] = 1;
    }
    if (s[0] == 'P') {
        f[0][2] = 0;
        f[0][3] = 1;
    }
    if (s[0] == 'S') {
        f[0][1] = 1;
        f[0][3] = 0;
    }
    for (int i = 1; i < n; i++) {
        if (s[i] == 'R') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]);
            f[i][2] = max(f[i - 1][1], f[i - 1][3]) + 1;
        }
        if (s[i] == 'P') {
            f[i][2] = max(f[i - 1][1], f[i - 1][3]);
            f[i][3] = max(f[i - 1][1], f[i - 1][2]) + 1;
        }
        if (s[i] == 'S') {
            f[i][1] = max(f[i - 1][2], f[i - 1][3]) + 1;
            f[i][3] = max(f[i - 1][1], f[i - 1][2]);
        }
    }
    cout << max({f[n - 1][1], f[n - 1][2], f[n - 1][3]});
    return 0;
}